/**
 * 
 */
package combinatorics.passed;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author xyyi
 *
 */
public class CombinationSum {
	/**
	Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

	The same repeated number may be chosen from C unlimited number of times.

	Note:

	All numbers (including target) will be positive integers.
	Elements in a combination (a1, a2, � , ak) must be in non-descending order. (ie, a1 ? a2 ? � ? ak).
	The solution set must not contain duplicate combinations.
	For example, given candidate set 2,3,6,7 and target 7, 
	A solution set is: 
	[7] 
	[2, 2, 3] 
	 */
	public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates,
			int target) {
		Arrays.sort(candidates);
		ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		combinationSum2(candidates, list, 0, target, results);
		return results;
	}

	// DFS
	private void combinationSum(int[] candidates, ArrayList<Integer> list,
			int index, int target, ArrayList<ArrayList<Integer>> results) {
		if (target < 0)
			return;
		if (target == 0) {
			results.add(new ArrayList<Integer>(list));
		} else {
			for (int i = index; i < candidates.length; i++) {
				list.add(candidates[i]);
				combinationSum(candidates, list, i, target - candidates[i],
						results);
				list.remove(list.size() - 1);
			}
		}
	}

	/**
	Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

	Each number in C may only be used once in the combination.

	Note:

	All numbers (including target) will be positive integers.
	Elements in a combination (a1, a2, � , ak) must be in non-descending order. (ie, a1 ? a2 ? � ? ak).
	The solution set must not contain duplicate combinations.
	For example, given candidate set 10,1,2,7,6,1,5 and target 8, 
	A solution set is: 
	[1, 7] 
	[1, 2, 5] 
	[2, 6] 
	[1, 1, 6] 
	 */
	private void combinationSum2(int[] candidates, ArrayList<Integer> list,
			int index, int target, ArrayList<ArrayList<Integer>> results) {
		if (target < 0) {
			return;
		} else if (target == 0) {
			results.add(new ArrayList<Integer>(list));
		} else {
			for (int i = index; i < candidates.length; i++) {
				list.add(candidates[i]);
				combinationSum2(candidates, list, i + 1,
						target - candidates[i], results);
				list.remove(list.size() - 1);
				while (i < candidates.length - 1
						&& candidates[i] == candidates[i + 1]) {
					i++;
				}
			}
		}
	}

	/**
	 * 
	 */
	public CombinationSum() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CombinationSum cs = new CombinationSum();

		//		int[] candidates = new int[] { 10, 1, 2, 7, 6, 1, 5, 8 };
		//		int target = 8;

		int[] candidates = new int[] { 7 };
		int target = 7;

		ArrayList<ArrayList<Integer>> results = cs.combinationSum(candidates,
				target);
		cs.print(results);
	}

	private void print(ArrayList<ArrayList<Integer>> result) {
		System.out.printf("Total: %d\n", result.size());
		for (ArrayList<Integer> arr : result) {
			for (Integer i : arr) {
				System.out.printf("%d,", i);
			}
			System.out.println();
		}
	}

}
